Recent developments in cryptography theory demonstrate how information theoretic secrecy can be generated from publicly accessible sources of randomness under the assumption that the potential attacker/eavesdropper's storage capability is bounded (although potentially quite large). These developments may be particularly well-suited for use in secrecy generation in wireless communication systems due to the natural broadcast nature of the wireless communication medium.
An approach to generate common secrecy from the correlation inherent in reciprocal wireless channels has been presented before and disclosed in copending and commonly assigned U.S. patent application Ser. Nos. 60/826,484 filed on Sep. 21, 2006; 60/751,803 filed on Dec. 20, 2005; 60/819,023 filed on Jul. 7, 2006; 11/444,558 filed on May 31, 2006; and 11/339,958 filed on Jan. 26, 2006. This secrecy approach exploits a joint randomness not shared with others (JRNSO) characteristic of a unique channel response between wireless nodes. However, the randomness generated using this approach is typically low-rate and has relatively specific applications.
Information-theoretic security can be derived from a public (and therefore completely non-secret) source of randomness under just a bounded storage assumption on the eavesdropper. FIG. 1 shows an example of a wireless system in which bounded storage based information-theoretic security could be used to protect communications between Alice and Bob, from being discovered by Eve. The process involves two steps: sampling the random stream and extracting a “pure secret” from the sampled data. To completely understand the mathematics, the following notations are applicable:                T: the overall duration of a session        α: public stream rate        β: input randomness/secrecy rate        γ: average/amortized rate at which the legitimate parties (Alice/Bob) can sample the public stream. If they can read at different rates, this is the minimum of the two.        N: Total data available during a sessionN=αT  (1)        k: Shared secret lengthk=βT  (2)        n: Total number of bits Alice and Bob can sample togethern=γT  (3)        n0: Total number of bits Alice and Bob can sample per block for block-wise algorithms. Since we have some freedom in choosing the block length (i.e. choosing T), we assume w.l.og. that n/n0 and N/(n/n0) are integers.        
      N    0    =      N          n      /              n        0            total number of bits in each of the blocks for block-wise algorithms.                b: The portion of total data that the attacker (Eve) is assumed to be able to store (i.e. 0<b<1). This is a parameter used in the analysis.        G: Attacker's actual storage capacity. This is the actual state of affairs. The relationship between G and b establishes one of the constraints driving the problem.G=bN  (4)        α: Implementation back-off parameter. This is the implementation loss suffered for having a finite block length, not using theoretically ideal samplers, etc.        ε: Probability of error in the algorithm process (probability that Alice and Bob fail to arrive at joint randomness or that it is not secret from Eve).        l: Total number of secret bits generated by Alice and Bob in addition to the k bits available at the onset.        
Sampling is the key procedure through which generation of randomness is assured. The process occurs during pre-defined time intervals, called sessions, each session is of time duration T. The data during a session can therefore be considered to be a block of length N.
In the example of FIG. 2, Alice and Bob sample the public random stream in a way that is unknown to Eve until the end of the session. Moreover, taking into account Eve's limited storage capability, the sampling should be done in such a way that it is highly unlikely Eve will have stored all of the sampled bits at the end of the sampling procedure, no matter what selective storage strategy Eve utilizes. Since Eve knows that she cannot store the complete stream, Eve's best chance to eavesdrop is to selectively sample bits, and hope that she retains the same bits sampled by Alice and Bob. Alice and Bob don't know Eve's sampling strategy, but nevertheless select their own sampling strategy so that it is likely that at least some of their data has not been stored by Eve.
To accomplish this, Alice and Bob have to sample randomly and must therefore have some way of agreeing on how they can randomly sample the same bits so that they remain completely secret from Eve, at least until the end of the session. For the purposes of this example, it is assumed that such input randomness is made available to Alice and Bob only at a finite rate β or in finite blocks of k bits per session.
Also, Alice and Bob may themselves be limited in either what they can store: the parameter n representing the minimum of their limitations; or how often they can sample on average the parameter γ representing the least of their average sampling rates.
A very simple example of a sampling procedure for Alice and Bob is then as follows: (1) Alice and Bob divide the session into n/n0 sub-sessions, where in each sub-session they sample n0 bits; (2) the shared random bits are then used to define the positions. For example, Alice and Bob partition the N-bit sub-session of public random data in N0 blocks of
      N    0    =      N          n      /              n        0            bits each. Then Alice and Bob use their shared random secret to select the same n0 positions within each sub-session. Since the index of each position requires log N0 bits, n0 log N0 total bits are needed. Therefore, the first requirement of this example is k>n0 log N0. The inequality must in fact be strict since of the k available random bits some bits are required for extraction and these should not be reused for sampling.
It should be noted that while the size of each individual sub-session can be less than Eve's storage limit (i.e. we are permitted to have N0<G), the total constraint N>G must still remain. Moreover, if the bits used to sample the stream are to be revealed, they cannot be revealed until the complete session is over.
While the sampling method outlined above is preferable because of its simplicity as well as relatively good performance, other sampling methods for the bound storage model (BSM) problem are known in the art.
Extraction, as applicable in the example of FIG. 1, is a problem of taking X perfectly random bits of which partial information is known to the adversary. The information known is quantified as no more than Y bits (of entropy). The problem is then to extract (X-Y) bits completely secret from the adversary.
Various methods exist, all of which require access to a certain amount of perfect shared randomness, which can be secret or revealed to the eavesdropper. In general, at least a number of extraction bits are needed as follows:
                              Number          ⁢                                          ⁢          of          ⁢                                          ⁢          Extraction          ⁢                                          ⁢          bits                =                              log            ⁢                                                                      ⁢                                                                    ⁢            n                    +                      log            ⁢                                                  ⁢                          1              /              ɛ                                                          (        5        )            where ε is the error inherent in the extraction process. Any example calculation herein will use this value; actual implementations will, of course, vary based on what technique is actually used.
Although, it is clear that the bounded storage model (BSM) work will mathematically, there is a need for practical implementations for performing BSM secrecy generation. With respect to the example above it would be beneficial to provide a short common secret to Alice and Bob, as well as a reliable source of public randomness.